//现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
//
// 给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
//
// 请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种
// 顺序即可。
//
// 字符串 s 字典顺序小于 字符串 t 有两种情况：
//
//
// 在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
// 如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
//
//
//
//
// 示例 1：
//
//
//输入：words = ["wrt","wrf","er","ett","rftt"]
//输出："wertf"
//
//
// 示例 2：
//
//
//输入：words = ["z","x"]
//输出："zx"
//
//
// 示例 3：
//
//
//输入：words = ["z","x","z"]
//输出：""
//解释：不存在合法字母顺序，因此返回 "" 。
//
//
//
//
// 提示：
//
//
// 1 <= words.length <= 100
// 1 <= words[i].length <= 100
// words[i] 仅由小写英文字母组成
//
//
//
//
//
// 注意：本题与主站 269 题相同： https://leetcode-cn.com/problems/alien-dictionary/
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 数组 字符串 👍 143 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function alienOrder(words: string[]): string {
    /*
    ? 遍历words统计所有出现的字母
    ? 遍历words中相邻的每对儿，统计这两对儿字典序不同的原因（第一个出现不同的地方，如果都一样且前面的长，可以直接返回）
    ? 从所有没有入度的字母开始，拓扑遍历所有转移（因为转移是满足字典序的，入度为0时加入的话，所有字典序比它小的都已经加入了，可以加入）
     */
    const set = new Set<string>(), graph = new Map<string, Array<string>>(), d = new Array<number>(26).fill(0)
    out:
        for(let i = 0; i < words.length; i++) {
            for(let j = 0; j < words[i].length; j++) {
                set.add(words[i].charAt(j))
            }
            if(i < words.length - 1) {
                for(let j = 0; j < Math.min(words[i].length, words[i + 1].length); j++) {
                    if(words[i].charCodeAt(j) != words[i + 1].charCodeAt(j)) {
                        if(graph.has(words[i].charAt(j))) {
                            graph.get(words[i].charAt(j)).push(words[i + 1].charAt(j))
                        } else {
                            graph.set(words[i].charAt(j), [words[i + 1].charAt(j)])
                        }
                        d[words[i + 1].charCodeAt(j) - 'a'.charCodeAt(0)]++
                        continue out
                    }
                }
                if(words[i].length > words[i + 1].length) {
                    return ""
                }
            }
        }
    const ans = new Array()
    for(const c of set) {
        if(d[c.charCodeAt(0) - 'a'.charCodeAt(0)] == 0) {
            ans.push(c)
        }
    }
    for(let i = 0; i < ans.length; i++) {
        const c = ans[i]
        if(graph.has(c)) {
            for(const nxt of graph.get(c)) {
                if(--d[nxt.charCodeAt(0) - 'a'.charCodeAt(0)] == 0) {
                    ans.push(nxt)
                }
            }
        }
    }
    return ans.length == set.size ? ans.join("") : "";
};

//leetcode submit region end(Prohibit modification and deletion)
